


#include <iostream>
#include <vector>
#include <queue>
using namespace std;

 struct TreeNode 
 {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
 
class Solution
{
    using Node = TreeNode;
public:
    int minDepth1(TreeNode* root)
    {
        if (!root)
            return 0;

        int res = INT_MAX;
        int pathcnt = 0;

        _minDepth1(root, pathcnt, res);

        return res;
    }

    int minDepth2(TreeNode* root)
    {
        if (!root)
            return 0;
        if (!root->left && !root->right)
            return 1;

        int left = minDepth2(root->left);
        int right = minDepth2(root->right);

        if (!(root->left && root->right))
            return max(left, right) + 1;
        else // if ((!root->left && !root->right) || (root->left || root->right))
            return min(left, right) + 1;
    }

    vector<double> averageOfLevels(TreeNode* root)
    {
        queue<Node*> q;
        vector<double> res;

        q.push(root);
        res.reserve(1e4);

        for (Node* cur = root, *front = nullptr; q.size();)
        {
            long long sum = 0;
            int n = q.size();

            for (int i = 0; i < n; ++i)
            {
                front = q.front();
                q.pop();
                sum += front->val;

                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }

            res.push_back((double)sum / n);
        }

        return res;
    }

    bool isUnique1(string astr)
    {
        if (!astr.size())
            return true;

        for (int i = 0, n = astr.size(); i < n; ++i)
        {
            int cnt = 0;

            for (int j = 0; j < n; ++j)
            {
                if (astr[i] == astr[j])
                    ++cnt;
            }
            if (cnt > 1)
                return false;
        }

        return true;
    }

    bool isUnique2(string astr)
    {
        int bitmap = 0;
        int n = astr.size();

        if (!n)
            return true;

        for (auto e : astr)
        {
            int index = e - 'a';

            // if ((bitmap >> index) & 1u)
            //     return false;
            // else
            //     bitmap |= 1u << index;
            if ((bitmap >> index) & 1u)
                return false;
            bitmap |= 1u << index;
        }
        
        return true;
    }

    int missingNumber1(vector<int>& nums)
    {
        int miss = 0;
        int n = nums.size();

        for (int i = 0; i <= n; ++i)
        {
            miss ^= i;
        }
        for (auto e : nums)
        {
            miss ^= e;
        }

        return miss;
    }

    vector<int> missingTwo1(vector<int>& nums)
    {
        int n = nums.size();
        int bit1 = 0, xorsum = 0;

        for (int i = 1; i <= n + 2; ++i)
        {
            xorsum ^= i;
        }
        for (auto e : nums)
        {
            xorsum ^= e;
        }
        for (int i = 0; i < 31; ++i)
        {
            if ((xorsum >> i) & 1U)
            {
                bit1 = i;
                break;
            }
        }

        int a = 0, b = 0;
        for (auto e : nums)
        {
            if (e & (1U << bit1))
                a ^= e;
            else
                b ^= e;
        }
        for (int i = 1; i <= n + 2; ++i)
        {
            if (i & (1U << bit1))
                a ^= i;
            else
                b ^= i;
        }

        return { a, b };
    }

    int singleNumber1(vector<int>& nums)
    {
        int res = 0;

        for (int i = 0, sum = 0; i < 32; ++i)
        {
            sum = 0;

            for (auto e : nums)
            {
                sum += (e >> i) & 1u;
            }
            if (sum % 3)
                res |= (1u << i);
        }

        return res;
    }

    int getSum(int a, int b)
    {
        while (b)
        {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }

        return a;
    }

private:
    void _minDepth1(Node* root, int& pathcnt, int& res)
    {
        if (!root)
            return;

        ++pathcnt;
        _minDepth1(root->left, pathcnt, res);
        _minDepth1(root->right, pathcnt, res);

        if (!root->left && !root->right)
            res = min(pathcnt, res);
        --pathcnt;
    }
};

int main()
{


	return 0;
}